package com.zs.letcode.illustration_of_algorithm;

/**
 * 剑指 Offer 56 - II. 数组中数字出现的次数 II
 * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [3,4,3,3]
 * 输出：4
 * 示例 2：
 * <p>
 * 输入：nums = [9,1,7,9,7,9,7]
 * 输出：1
 *
 * <p>
 * 限制：
 * <p>
 * 1 <= nums.length <= 10000
 * 1 <= nums[i] < 2^31
 *
 * <p>
 * 相关标签
 * 位运算
 * 数组
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/9hyq1r/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/29 09:02
 */
public class Chapter64 {
    public static void main(String[] args) {

    }

    private class Solution {
        /**
         * 方法一：有限状态自动机
         */
        public int singleNumber(int[] nums) {
            int ones = 0, twos = 0;
            for (int num : nums) {
                ones = ones ^ num & ~twos;
                twos = twos ^ num & ~ones;
            }
            return ones;
        }

        /**
         * 方法二：遍历统计
         */
        public int singleNumber1(int[] nums) {
            int[] counts = new int[32];
            for (int num : nums) {
                for (int i = 0; i < 32; i++) {
                    counts[i] += num & 1; // 更新第 i 位 1 的个数之和
                    num >>= 1;            // 第 i 位 --> 第 i 位
                }
            }
            int res = 0, m = 3;
            for (int i = 31; i >= 0; i--) {
                res <<= 1;
                res |= counts[i] % m;     // 恢复第 i 位
            }
            return res;
        }
    }
}
